#pragma once


#include "3DType.h"

#include <vector>
#include <list>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cmath>

class Scan
{
	struct Point
	{
		Point():x(0),y(0){}
		Point(int _x,int _y):x(_x),y(_y){}
		int x;
		int y;
	};

	struct ScanLine
	{
		int y;
		int x_start;
		int x_end;
	};

	typedef std::vector<Point> PtList;
	typedef std::queue<ScanLine> ScanLineQueue;

	class pt_greater
	{
	public:
		pt_greater(const PtList* ptlist):m_List(ptlist){}
		bool operator()(unsigned int index_left,unsigned int index_right)
		{
			return	(*m_List)[index_left].y > (*m_List)[index_right].y
					|| (*m_List)[index_left].y == (*m_List)[index_right].y && (*m_List)[index_left].x > (*m_List)[index_right].x ;
		}

	private:
		const PtList* m_List;
	};

	struct ActiveLine
	{
		ActiveLine():start_id(0),end_id(0),delta_x(0),current_x(0){}
		ActiveLine(unsigned int _start,unsigned int _end,double _delta,double _current)
			:start_id(_start),end_id(_end),delta_x(_delta),current_x(_current){}
		unsigned int start_id;
		unsigned int end_id;
		double delta_x;
		double current_x;
	};

	typedef std::list<ActiveLine> ActiveLineList;
public:
	Scan(void)
	{
		clear();
	}
	~Scan(void){}



	void clear()
	{
		m_PtList.clear();
		m_PtSortY.clear();
		m_ActiveLineList.clear();
		while(!m_ScanLineQueue.empty()) m_ScanLineQueue.pop();

		m_CurrentY = 0;
		enumerating = false;
	}
	void reset()
	{
		enumerating = false;
	}
	bool next(int* x, int* y)
	{
		if ( m_PtList.size() < 2 ) return false;
		if ( !enumerating )
		{
			_begin_enum();
			_update_active();
			if ( m_ActiveLineList.empty() )
			{
				std::vector<unsigned int> ptsorty;
				for(size_t i=0;i<m_PtList.size();++i)
				{
					ptsorty.push_back(i);
				}
				std::sort(ptsorty.begin(),ptsorty.end(),pt_greater(&m_PtList));

				ScanLine line;
				line.x_start = m_PtList[ptsorty.back()].x;
				line.x_end = m_PtList[ptsorty.front()].x;
				line.y = m_CurrentY;
				m_ScanLineQueue.push(line);
			}
			else
			{
				_push_scan_line();
			}
		}
		else
		{
			if ( m_ScanLineQueue.front().x_start > m_ScanLineQueue.front().x_end )
			{
				m_ScanLineQueue.pop();
			}
			
			if ( m_ScanLineQueue.empty() )
			{
				if ( m_ActiveLineList.empty() ) return false;
				_advance_active_line();
				_push_scan_line();
				_update_active();
			}
		}		
		
		*x = m_ScanLineQueue.front().x_start++;
		*y = m_ScanLineQueue.front().y;
		return true;
	}

	void push_back(int x,int y)
	{
		m_PtList.push_back(Point(x,y));
	}

	size_t size()const
	{
		return m_PtList.size();
	}
private:
	void _begin_enum()
	{
		m_PtSortY.clear();
		for(size_t i=0;i<m_PtList.size();++i)
		{
			m_PtSortY.push_back(i);
		}
		std::sort(m_PtSortY.begin(),m_PtSortY.end(),pt_greater(&m_PtList));

		for(size_t i=0;i<m_PtList.size();++i)
		{
			std::cout<<m_PtList[m_PtSortY[i]].x<<" "<<m_PtList[m_PtSortY[i]].y<<std::endl;
		}

		m_CurrentY = m_PtList[m_PtSortY.back()].y;

		enumerating = true;
	}

	void _update_active()
	{
		while ( !m_PtSortY.empty()  )
		{
			if ( m_CurrentY == m_PtList[m_PtSortY.back()].y )
			{
				_remove_exist_active(m_PtSortY.back());
				_push_new_active(m_PtSortY.back());
				m_PtSortY.pop_back();
			}
			else
			{
				break;
			}
		}
	}

	void _remove_exist_active(unsigned int id)
	{
		ActiveLineList::iterator it = m_ActiveLineList.begin();
		while ( it != m_ActiveLineList.end())
		{
			int left = (id + m_PtList.size() - 1) % m_PtList.size();
			int right = (id+1) % m_PtList.size();
			if ( it->start_id == left && it->end_id == id 
				|| it->start_id == right && it->end_id == id ) 
			{
				it = m_ActiveLineList.erase(it);
			}
			else
			{
				++it;
			}
		}
	}

	void _push_new_active(unsigned int id)
	{
		pt_greater greater(&m_PtList);

		int left = (id + m_PtList.size() - 1) % m_PtList.size();
		int right = (id+1) % m_PtList.size();

		if ( greater(left,id) )
		{
			int y_diff = m_PtList[left].y - m_PtList[id].y;
			if ( y_diff != 0 )
			{
				double delta = (double)(m_PtList[left].x - m_PtList[id].x) /  y_diff;
				double start = m_PtList[id].x;
				m_ActiveLineList.push_back(ActiveLine(id,left,delta,start));
			}
		}

		if ( greater(right,id) )
		{
			int y_diff = m_PtList[right].y - m_PtList[id].y;
			if ( y_diff != 0 )
			{
				double delta = (double)(m_PtList[right].x - m_PtList[id].x) /  y_diff;
				double start = m_PtList[id].x;
				m_ActiveLineList.push_back(ActiveLine(id,right,delta,start));
			}
		}
	}

	void _advance_active_line()
	{
		++m_CurrentY;
		for(ActiveLineList::iterator it = m_ActiveLineList.begin();it != m_ActiveLineList.end();++it)
		{
			it->current_x += it->delta_x;
		}
	}

	void _push_scan_line()
	{
		ActiveLineList::iterator it = m_ActiveLineList.begin();
		while( it != m_ActiveLineList.end())
		{
			ActiveLine& left = *it;
			++it;
			ActiveLine& right = *it;
			++it;
			
			ScanLine line;
			line.x_start = round( min(right.current_x,left.current_x) );
			line.x_end = round( max(right.current_x,left.current_x) );
			line.y = m_CurrentY;

			m_ScanLineQueue.push(line);
		}
	}

	PtList m_PtList;
	std::vector<unsigned int> m_PtSortY;
	ActiveLineList m_ActiveLineList;
	ScanLineQueue m_ScanLineQueue;

	int m_CurrentY;
	bool enumerating;
};
